package com.lh.jianzhioffer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: linghao
 * @since: 2023/2/12
 *
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，
 * 每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null
 *
 */
public class 复杂链表的复制35 {

    //回溯+递归，用hash判断还没有创建的node，再用递归去创建
    Map<Node,Node> cacheNode = new HashMap<>();

    public Node copyRandomList(Node head) {
        if(head == null)return null;
        if(!cacheNode.containsKey(head)){
            Node newNode = new Node(head.val);
            cacheNode.put(head,newNode);
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);
        }
        return cacheNode.get(head);
    }


    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
